package com.mypaper.dag;

import com.mypaper.elem.TaskAttribute;
import com.mypaper.list.ListPriority;
import com.mypaper.list.UnorderLinkedList;

public class RefactorDAG
{
	public int vertexNum;
	public int procNum;
	public float[] vertexAverWeight;
	public float[][] vertexWeight;
	public float[][] edgeWeight;
	public float[][] edgeWeightRefactor;
	public float[][] vertexWeightRefactor;
	public float[] vertexAverWeightRefactor;
	public float[] btLevel;
	public float CPLength=0;
	public ListPriority prior; //HEFT优先级
	public ListPriority priorRever;//HEFT的反队列
	public ListPriority priorHTR;//HTR优先级
	public ListPriority priorReverHTR;
	public UnorderLinkedList[] HTRCPList;//重构关键路径队列
	public int[] outDegree;
	public int[] inDegree;
	public int[] outDegreeHTR;
	public int[] inDegreeHTR;
	public int countOfCP = 0;
	public int countOfDel = 0;
	public String[][] merge = null; //用来存储各路径上能合并的任务集
	public int indexCP = 0;//用来标记CP中的任务，确保优先级相同的任务在一条路径上；
	
	
	public RefactorDAG(){
		vertexNum=0;
		procNum=0;
		prior=new ListPriority();
		vertexWeight=new float[vertexNum][procNum];
		
		float sum;
		for(int i=0; i<vertexNum; i++){
			sum=0;
			for(int j=0; j<procNum; j++){
				sum+=vertexWeight[i][j];
			}
			vertexAverWeight[i]=sum/procNum;
		}
		edgeWeight=new float[vertexNum][vertexNum];
	}
	
	public RefactorDAG(int vertexNum, int procNum, float[][] vertexWeight, float[][] edgeWeight){
		this.vertexNum=vertexNum;
		this.procNum=procNum;
		this.vertexWeight=new float[vertexNum][procNum];
		this.vertexWeightRefactor = new float[vertexNum][procNum];
		this.vertexAverWeight=new float[vertexNum];
		this.vertexAverWeightRefactor = new float[vertexNum];
		this.edgeWeight=new float[vertexNum][vertexNum];
		this.edgeWeightRefactor = new float[vertexNum][vertexNum];
		this.prior = new ListPriority();
		this.priorRever = new ListPriority();
		this.priorHTR = new ListPriority();
		this.priorReverHTR = new ListPriority();
		this.outDegree=new int[vertexNum];
		this.inDegree=new int[vertexNum];
		this.inDegreeHTR = new int[vertexNum];
		this.outDegreeHTR = new int[vertexNum];
		this.HTRCPList = new UnorderLinkedList[vertexNum];
		this.merge = new String[vertexNum][vertexNum];
		for(int i = 0; i < vertexNum; i++)
		{
			HTRCPList[i] = new UnorderLinkedList();
		}
		for(int i=0; i<vertexNum; i++)
			for(int j=0; j<vertexNum; j++){
				if(edgeWeight[i][j]!=0)
				{
					outDegree[i]++;
					outDegreeHTR[i]++;
				}
					
				if(edgeWeight[j][i]!=0)
				{
					inDegree[i]++;
					inDegreeHTR[i]++;
				}
					
			}
		for(int i=0; i<vertexNum; i++)
			for(int j=0; j<procNum; j++)
			{
				this.vertexWeight[i][j]=vertexWeight[i][j];
				this.vertexWeightRefactor[i][j] = vertexWeight[i][j];
			}
		
		for(int i=0; i<vertexNum; i++)
			for(int j=0; j<vertexNum; j++){
				this.edgeWeight[i][j]=edgeWeight[i][j];
				this.edgeWeightRefactor[i][j] = edgeWeight[i][j];
			}
		float sum;
		for(int i=0; i<vertexNum; i++){
			sum=0;
			for(int j=0; j<procNum; j++){
				sum+=vertexWeight[i][j];
			}
			vertexAverWeight[i]=sum/procNum;
			vertexAverWeightRefactor[i] = sum/procNum;
			System.out.print("<"+ i + ":"+sum/procNum+"> ");//打印平均顶点权重
		}
		System.out.println();
	}
	
	public float[] bLevelCal(){
		float[] blevel=new float[vertexNum];
		float maxBSucc=0;
		int[] outDegreeBack=new int[vertexNum];
		for(int i=0; i<vertexNum; i++)
			outDegreeBack[i]=outDegree[i];
		
		for(int i=0; i<vertexNum; i++){
			for(int j=vertexNum-1; j>=0; j--){
				if(outDegreeBack[j]==0){
					maxBSucc=0;
					for(int k=0; k<vertexNum; k++){
						if(edgeWeight[j][k]!=0){
							if(maxBSucc<edgeWeight[j][k]+blevel[k]){
								maxBSucc=edgeWeight[j][k]+blevel[k];
							}
						}
					}
					blevel[j]=vertexAverWeight[j]+maxBSucc;
					outDegreeBack[j]--;
					for(int k=0; k<vertexNum; k++){
						//当前节点的父节点出度减一
						if(edgeWeight[k][j]!=0 && outDegreeBack[k]>=0)
							outDegreeBack[k]--;
					}
					break;
				}
			}
		}
		return blevel;
	}
	
	public float[] tLevelCal(){
		float[] tlevel=new float[vertexNum];
		float maxTPrev=0;
		int[] inDegreeBack=new int[vertexNum];
		for(int i=0; i<vertexNum; i++)
			inDegreeBack[i]=inDegree[i];
		
		for(int i=0; i<vertexNum; i++){
			for(int j=0; j<vertexNum; j++){
				if(inDegreeBack[j]==0){
					maxTPrev=0;
					for(int k=0; k<vertexNum; k++){
						if(edgeWeight[k][j]!=0){
							if(maxTPrev<edgeWeight[k][j]+vertexAverWeight[k]+tlevel[k]){
								maxTPrev=edgeWeight[k][j]+vertexAverWeight[k]+tlevel[k];
							}
						}
					}
					tlevel[j]=maxTPrev;
					inDegreeBack[j]--;
					for(int k=0; k<vertexNum; k++){
						//当前节点的父节点出度减一
						if(edgeWeight[j][k]!=0 && inDegreeBack[k]>=0)
							inDegreeBack[k]--;
					}
					break;
				}
			}
		}
		return tlevel;
	}
	
	public float[] HTRbLevelCal(){
		float[] blevel=new float[vertexNum];
		float maxBSucc=0;
		int[] outDegreeBack=new int[vertexNum];
		for(int i=0; i<vertexNum; i++)
		{
			outDegreeBack[i]=outDegreeHTR[i];
		    //System.out.println(i+":out:"+ outDegreeBack[i]);
		}
		for(int i=0; i<vertexNum; i++){
			for(int j=vertexNum-1; j>=0; j--){
				if(outDegreeBack[j]==0){
					maxBSucc=0;
					for(int k=0; k<vertexNum; k++){
						if(edgeWeightRefactor[j][k]!=0){
							if(maxBSucc<edgeWeightRefactor[j][k]+blevel[k]){
								maxBSucc=edgeWeightRefactor[j][k]+blevel[k];
							}
						}
					}
					blevel[j]=vertexAverWeightRefactor[j]+maxBSucc;
					outDegreeBack[j]--;
					for(int k=0; k<vertexNum; k++){
						//当前节点的父节点出度减一
						if(edgeWeightRefactor[k][j]!=0 && outDegreeBack[k]>=0)
							outDegreeBack[k]--;
					}
					break;
				}
			}
		}
//		System.out.println("测试合并后的Blevel：");
//		for(int i = 0; i < vertexNum; i++)
//			System.out.println(i+ ":" +blevel[i]);
		return blevel;
	}
	
	public float[] HTRtLevelCal(){
		float[] tlevel=new float[vertexNum];
		float maxTPrev=0;
		int[] inDegreeBack=new int[vertexNum];
		for(int i=0; i<vertexNum; i++)
			inDegreeBack[i]=inDegreeHTR[i];
		
		for(int i=0; i<vertexNum; i++){
			for(int j=0; j<vertexNum; j++){
				if(inDegreeBack[j]==0){
					maxTPrev=0;
					for(int k=0; k<vertexNum; k++){
						if(edgeWeightRefactor[k][j]!=0){
							if(maxTPrev<edgeWeightRefactor[k][j]+vertexAverWeightRefactor[k]+tlevel[k]){
								maxTPrev=edgeWeightRefactor[k][j]+vertexAverWeightRefactor[k]+tlevel[k];
							}
						}
					}
					tlevel[j]=maxTPrev;
					inDegreeBack[j]--;
					for(int k=0; k<vertexNum; k++){
						//当前节点的父节点出度减一
						if(edgeWeightRefactor[j][k]!=0 && inDegreeBack[k]>=0)
							inDegreeBack[k]--;
					}
					break;
				}
			}
		}
		return tlevel;
	}
	
	public void proirBLevel(){//HEFT优先级
		float[] bLevel=bLevelCal();
		TaskAttribute task=new TaskAttribute();
		for(int i=0; i<vertexNum; i++){
			task.setAttribute(i, bLevel[i]);
			prior.enDownList(task);
			priorRever.enUpList(task);
		}
	}
	
	public void printPrior(){
		prior.print();
	}
	
	//重构的整个过程
	public void HTRCP(){
//		countOfDel = 0;
//		countOfCP = 0;
		while(countOfDel < vertexNum)
		{
			float[] bLevel=HTRbLevelCal();
			float[] tLevel=HTRtLevelCal();
		    //System.out.println("----countOfDel-----" + countOfDel +"------------");
			btLevel=new float[vertexNum];
			for(int i=0; i<vertexNum; i++){
				btLevel[i]=bLevel[i]+tLevel[i];
//				System.out.println("bLevel["+i+"]="+bLevel[i]);
//				System.out.println("tLevel["+i+"]="+tLevel[i]);
//				System.out.println("btLevel["+i+"]="+btLevel[i]);System.out.println();
			}
		
			TaskAttribute task=new TaskAttribute();
			CPLength = 0;
			for(int i=0; i<vertexNum; i++){
				
				if(CPLength<btLevel[i]){
					CPLength=btLevel[i];
				}
			}
			boolean isFirstTask = true;
			for(int i=0; i<vertexNum; i++)
			{
				if(isFirstTask && Math.abs(btLevel[i]-CPLength)<0.0001)//标记第一个任务
				{
					indexCP = i;
					task.setAttribute(i, btLevel[i]);
					HTRCPList[countOfCP].insertNode(task);//插入到队列
					isFirstTask = false;
				}
				if(Math.abs(btLevel[i]-CPLength)<0.0001 && edgeWeight[indexCP][i] != 0)//找CP上的任务
				{
					indexCP = i;
					task.setAttribute(i, btLevel[i]);
					HTRCPList[countOfCP].insertNode(task);//插入到队列
				}
			}
			System.out.println("<---##### CP:"+countOfCP);//打印CP；
			HTRCPList[countOfCP].print();
			System.out.println("#### CP:end " +countOfCP + "--->");
			DelCPofDAG(HTRCPList[countOfCP]); //删除CP，从CP中选出能合并的节点
			countOfCP++;
		}
	
		DAGRefactor();//将DAG任务进行重构合并；
		
		//print();//打印测试的相关信息；
		
		proirOfHTR();//计算HTR优先级；
		System.out.println("HTR优先级测试：");
		priorHTR.print();
		System.out.println("HEFT优先级：");
		proirBLevel();
		prior.print();
	}
	
	public void proirOfHTR()
	{//HTR优先级
		float[] bLevel=HTRbLevelCal();
		TaskAttribute task=new TaskAttribute();
		for(int i=0; i<vertexNum; i++)
		{
			if(bLevel[i] == 0)continue;
			task.setAttribute(i, bLevel[i]);
			priorHTR.enDownList(task);
			priorReverHTR.enUpList(task);
		}
		//priorHTR.print();
		for(int i = 0; i < countOfCP; i++)
		{
			
			for(int j = 0; j < merge[i].length; j++)
			{
				if(merge[i][j] != null)
				{
//					System.out.println("merge["+i+"]["+j+"]"+merge[i][j]);
					String mergeTaskNo = merge[i][j];//CP上能合并的任务集；
					String[] TaskNo = mergeTaskNo.split(",");
					int intFirstNo = Integer.parseInt(TaskNo[0]);//合并到的节点的序号；
					for(int k = 1; k < TaskNo.length; k++)
					{
						int mergedIndex = Integer.parseInt(TaskNo[k]);//将被合并的顶点取出放回到DAG；
						task.setAttribute(mergedIndex, bLevel[intFirstNo] - k * 0.1);
						priorHTR.enDownList(task);
						priorReverHTR.enUpList(task);
					}
				}
			}
		}
		
	}
	
	public void print()//打印一些相关的测试信息
	{
		// 打印能合并的任务………………		
				for(int i = 0; i < countOfCP; i++)
				{
					for(int j = 0; j < merge[i].length; j++)
					{
						if(merge[i][j] != null)
						{
							System.out.println("CP:[" + i + "][" + j + "]--" + merge[i][j]);
							
						}
					}
				}
			//打印完毕………………	
				System.out.println("合并后的边权重edgeWeightRefactor：");
				for(int i = 0; i < vertexNum; i++)
				{
					for(int j = 0; j < vertexNum; j++)
					{
						System.out.print(edgeWeightRefactor[i][j] + " ");
					}
					System.out.println();
				}
				System.out.println();
				System.out.println("合并后的vertexAverWeightRefactor:");
				for(int i = 0; i <vertexNum; i++)
				{
					System.out.print(vertexAverWeightRefactor[i] + " ");
				}
				System.out.println();
				for(int i = 0; i < vertexNum; i++)
				{
					for(int j = 0; j < vertexNum; j++)
					{
						if(edgeWeightRefactor[i][j] > 0)
						{
							System.out.println(i + "-->" + j);
						}
					}
					
				}
//				for(int i = 0; i < vertexNum; i++)
//					System.out.print("("+ i +":in=" + inDegreeHTR[i] + " out=" +  outDegreeHTR[i] + ") ");
			System.out.println();	
	}
	
	public void DAGRefactor()//DAG重构
	{
		for(int i = 0; i < vertexNum; i++)
		{
			for(int j = 0; j < vertexNum; j++)
			{
				edgeWeightRefactor[i][j] = edgeWeight[i][j];
			}
			vertexAverWeightRefactor[i] = vertexAverWeight[i];
			inDegreeHTR[i] = inDegree[i];
			outDegreeHTR[i] = outDegree[i];
		//上下为：复制原来的DAG任务信息到HTR	
			for(int j = 0; j < procNum; j++)
			{
				vertexWeightRefactor[i][j] = vertexWeight[i][j];
			}
		}
		
		for(int i = 0; i < countOfCP; i++)//选取能够合并的节点进行合并
		{
			for(int j = 0; j < merge[i].length; j++)
			{
				if(merge[i][j] != null)
				{
					String mergeTaskNo = merge[i][j];
					String[] TaskNo = mergeTaskNo.split(",");
					int intFirstNo = Integer.parseInt(TaskNo[0]);
					for(int k = 1; k < TaskNo.length; k++)
					{
						int intTaskNo = Integer.parseInt(TaskNo[k]);
						vertexAverWeightRefactor[intFirstNo] += vertexAverWeightRefactor[intTaskNo];//将CP上的其他节点合并到首节点
						vertexAverWeightRefactor[intTaskNo] = 0;//合并后删除CP上的该节点，后面使用时利用初始vertexAverWeight[intFirstNo]，见后
						outDegreeHTR[intTaskNo] = 0;//删除被合并的节点的出度和入度；
						inDegreeHTR[intTaskNo] = 0;
						edgeWeightRefactor[intFirstNo][intTaskNo] = 0;//删除首节点到被合并节点的边依赖
						edgeWeightRefactor[Integer.parseInt(TaskNo[k-1])][intTaskNo] = 0;//删除CP中相邻两节点的依赖
					}
					for(int l = 0; l < vertexNum; l++)//更新合并后的边依赖
					{
						//更新首节点与其他顶点的依赖
						if(edgeWeightRefactor[intFirstNo][l] > 0)
						{
							if(edgeWeightRefactor[intFirstNo][l] + vertexAverWeight[intFirstNo] - vertexAverWeightRefactor[intFirstNo] > 0)//使用初始的vertexAverWeight[intFirstNo]，
							    edgeWeightRefactor[intFirstNo][l] = edgeWeightRefactor[intFirstNo][l] - vertexAverWeightRefactor[intFirstNo] + vertexAverWeight[intFirstNo];
							else
								edgeWeightRefactor[intFirstNo][l] = (float) 0.01;//用来表示依赖
						}
						
						//更新其他的被整合节点的边依赖到新节点：
						float tempWeightSum = (float) vertexAverWeight[intFirstNo];
						for(int k = 1; k < TaskNo.length; k++)
						{
							int intTaskNo = Integer.parseInt(TaskNo[k]);
							tempWeightSum += vertexAverWeight[intTaskNo];
							if(edgeWeightRefactor[intTaskNo][l] > 0)
							{
								//如果首节点和某节点有依赖关系，进行判断，并更新依赖
								if(edgeWeightRefactor[intTaskNo][l] - vertexAverWeightRefactor[intFirstNo] + tempWeightSum > 0)
									edgeWeightRefactor[intFirstNo][l] = edgeWeightRefactor[intTaskNo][l] - vertexAverWeightRefactor[intFirstNo] + tempWeightSum;//使用初始的vertexAverWeight[intFirstNo]，
								else
								    edgeWeightRefactor[intFirstNo][l] = (float) 0.01;//将被合并的节点与其他节点的依赖转换为与首节点依赖
								edgeWeightRefactor[intTaskNo][l] = 0;//消除初始的边依赖
							}
						}
					}
						
					
				}
			}
		}
		
		for(int i = 0; i < vertexNum; i++)
			for(int j = 0; j < vertexNum; j++)
			{
				outDegreeHTR[i] = 0;
				inDegreeHTR[j] = 0;
			}
		
		for(int i = 0; i < vertexNum; i++)
			for(int j = 0; j < vertexNum; j++)
			{
				if(edgeWeightRefactor[i][j] != 0)
				{
					outDegreeHTR[i]++;
					inDegreeHTR[j]++;
				}
			}
		
		
		
	}
	
	public void DelCPofDAG(UnorderLinkedList CPListTask)
	{
		UnorderLinkedList CPList = null;
		CPList = CPListTask;
		int indexOfHTR = -1;
//		System.out.println("CPList.length:" + CPList.length());
//		CPList.print();
		countOfDel += CPList.length();
		String taskSet = "";  //CP中的能合并的任务
		int taskSetCountOfCP = 0; //CP上能合并的任务的数量
		String taskTemp = ""; //
		int taskTempCount = 0;//用来记录读取的能够合并的任务数量
		boolean identified = true;//用来标记当前任务是否为CP中的第一个任务；
//		System.out.print("CP:");CPList.print();
			while(CPList.first != null)
			{
				indexOfHTR =((TaskAttribute)CPList.first.info).index;
				vertexAverWeightRefactor[indexOfHTR] = 0;
				for(int j = 0; j < procNum; j++)
				{
					vertexWeightRefactor[indexOfHTR][j] = 0;
				}
				for(int k = 0; k < vertexNum; k++)
				{
					if(edgeWeightRefactor[indexOfHTR][k] != 0)
					{
						edgeWeightRefactor[indexOfHTR][k] = 0;
						inDegreeHTR[k]--;
						//outDegreeHTR[indexOfHTR]--;
					}
					if(edgeWeightRefactor[k][indexOfHTR] != 0)
					{
						edgeWeightRefactor[k][indexOfHTR] = 0;
						outDegreeHTR[k]--;
					}
					inDegreeHTR[indexOfHTR] = 0;
					outDegreeHTR[indexOfHTR] = 0;
					
				}
		/***** 检索出能够进行合并的任务号，并存入merge中****/
				if(taskTempCount >= 1)  
				{
					taskSet += taskTemp;
				}
				if(inDegree[indexOfHTR] == 1 || identified == true)
				{
					identified = false;
					taskTemp = indexOfHTR + ",";
					taskTempCount++;
				}else
					if(taskTempCount >= 2)
					{
						System.out.println("merge:"+taskSet);
						merge[countOfCP][taskSetCountOfCP] = taskSet;
						taskSet = "";
						taskTempCount = 0;
						taskSetCountOfCP++;
					}else
					{
						taskSet = "";
						taskTemp = indexOfHTR + ",";
						taskTempCount = 1;
					//仅接下来的两行使合并任务只包括从顶点入度为零的顶点开始合并（取消注释生效），若注释，则使合并任务能包括顶点不为零的顶点
//						taskSet = "";
//						taskTempCount = 0;
					}
				CPList.first = CPList.first.next;
			}
			//合并任务，其中包括从顶点入度不为零的顶点开始合并
			if(taskTempCount >= 2)
			{
			    taskSet += taskTemp;
				System.out.println("merge:"+taskSet);
				merge[countOfCP][taskSetCountOfCP] = taskSet;
			}
		
	}

}
